package LearnDataStructure.b_散列结构.HashMap;

import LearnDataStructure.b_散列结构.HashSet.MyHashSet;
import LearnDataStructure.b_散列结构.MyHash;
import LearnDataStructure.b_散列结构.useNode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-05 14:32
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.b_散列结构.HashMap
 */

/**
 * 散列算法使用了：
 * 解决冲突使用了拉链法
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K, V> implements MyHash<K, V> {
    private int capacity = 16;
    private int size = 0;
    private useNode<K, V>[] buckets = new useNode[capacity];

    public MyHashMap(int capacity) {
        this.capacity = capacity;
    }

    public MyHashMap() {
    }

    public useNode<K, V>[] getBuckets() {
        return buckets;
    }

    public int getCapacity() {
        return capacity;
    }

    /**
     * 哈希函数
     * 也就是散列函数
     * @param key
     * @return
     */
    public int MyHash(K key) {
        int temp = 0;
        int seed = 31;//素数
        String str = key.toString();
        for (int i = 0; i < str.length(); i++) {
            temp = seed * temp + str.charAt(i);
        }
        return temp % capacity;
    }

    @Override
    public void put(K key, V value) {
        useNode<K, V> newNode = new useNode<>(key,value);
        int index = MyHash(key);
        if (buckets[index] == null) {//当前的坑有没有被占
            buckets[index] = newNode;//放入坑中
            size++;
        } else {
            useNode<K, V> p = buckets[index];//被占了，取出此坑的链表的首元素
            while (p != null) {
                K headKey = p.key;
                if (headKey == key || (headKey.hashCode() == key.hashCode() && headKey.equals(key))) {//判断key值是否相等；包含地址相等 和 数值相等
                    //key值相等，则更新此key值的value
                    p.value = value;
                    break;
                }
                if (p.next == null) {//判断是否走到了末尾
                    p.next = newNode;
                    newNode.pre = p;
                    size++;
                    break;
                }
                p = p.next;//顺着链表继续走
            }
        }
    }

    @Override
    public void putAll(MyHash<? extends K, ? extends V> map) {

    }

    /**
     * 按顺序找所有的key，逐一对比
     * @param key
     * @return
     */
    @Override
    public boolean containsKey(K key) {
        int index = MyHash(key);
        if (buckets[index] == null) {
            return false;
        } else {
            useNode<K, V> p = buckets[index];
            while (p != null) {
                K headKey = p.key;
                if (headKey == key || (headKey.hashCode() == key.hashCode() && headKey.equals(key))) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    /**
     * 只能查找所有的数据
     * 按顺序找呗
     * @param value
     * @return
     */
    @Override
    public boolean containsValue(V value) {
        for (int i = 0; i < capacity; i++) {
            if (buckets[i] != null) {
                useNode<K, V> p = buckets[i];
                while (p != null) {
                    if (p.value.equals(value)) {
                        return true;
                    }
                    p = p.next;
                }
            }
        }
        return false;
    }

    @Override
    public V get(K key) {
        int index = MyHash(key);
        if (buckets[index] == null) {
            return null;
        } else {
            useNode<K, V> p = buckets[index];
            while (p != null) {
                K currentKey = p.key;
                if (currentKey == key || (currentKey.hashCode() == key.hashCode() && currentKey.equals(key))) {
                    return p.value;
                }
                p = p.next;
            }
        }
        return null;
    }

    @Override
    public MyHashSet<K> keySet() {
        MyHashSet<K> hashSet = new MyHashSet<>();
        for (int i = 0; i < capacity; i++) {
            if (buckets[i] != null) {
                useNode<K,V> p = buckets[i];
                while (p != null) {
                    hashSet.add(p.key);
                    p = p.next;
                }
            }
        }
        return hashSet;
    }

    @Override
    public MyHashSet<V> values() {
        MyHashSet<V> hashSet = new MyHashSet<>();
        for (int i = 0; i < capacity; i++) {
            if (buckets[i] != null) {
                useNode<K,V> p = buckets[i];
                while (p != null) {
                    hashSet.add(p.value);
                    p = p.next;
                }
            }
        }
        return hashSet;
    }

    @Override
    public Iterator<useNode<K, V>> iterator() {
        return new MyHashMapIterator<K,V>(this);
    }

    @Override
    public V remove(K key) {
        int index = MyHash(key);
        if (buckets[index] == null) {
            return null;
        } else {
            useNode<K, V> p = buckets[index];
            while (p != null) {
                K currnetKey = p.key;
                if (currnetKey == key || (currnetKey.hashCode() == key.hashCode() && currnetKey.equals(key))) {
                    if (p.pre != null) {
                        p.pre.next = p.next;
                        p.next.pre = p.pre;

                        p.pre = null;
                        p.next = null;
                    } else {
                        buckets[index] = p.next;

                        p.next = null;
                    }
                    size--;
                    return p.value;
                }
                p = p.next;
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (int i = 0; i < capacity; i++) {
            buckets[i] = null;
        }
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < capacity; i++) {
            if (buckets[i] != null) {
                useNode<K, V> p = buckets[i];
                while (p != null) {
                    if (p.next == null && i == capacity - 1) {
                        builder.append("(" + p.key + ", " + p.value + ")");
                    }
                    builder.append("(" + p.key + ", " + p.value + "), ");
                    p = p.next;
                }
            }
        }
        String res = builder.append(
                " capacity = " + capacity +
                        ", size = " + size).toString();
        return res;
    }
}
